package zcw.com.lib_leet_code;

import zcw.com.lib_leet_code.util.Util;

/**
 * Created by 朱城委 on 2022/2/11.<br><br>
 *
 * 中等：最长递增子序列
 */
public class Topic300 {

    public static void main(String[] args) {
        BaseSolution solution = new Solution2();

        int[] array = new int[] {10,9,2,5,3,7,101,18};
        System.out.println(solution.lengthOfLIS(array));

        array = new int[] {0,1,0,3,2,3};
        System.out.println(solution.lengthOfLIS(array));

        array = new int[] {7,7,7,7,7,7,7};
        System.out.println(solution.lengthOfLIS(array));

        array = new int[] {4,10,4,3,8,9};
        System.out.println(solution.lengthOfLIS(array));

        array = new int[] {1,3,6,7,9,4,10,5,6};
        System.out.println(solution.lengthOfLIS(array));

        array = new int[] {3,5,6,2,5,4,19,5,6,7,12};
        System.out.println(solution.lengthOfLIS(array));
    }

    private interface BaseSolution {
        int lengthOfLIS(int[] nums);
    }

    private static class Solution1 implements BaseSolution {

        @Override
        public int lengthOfLIS(int[] nums) {
            int[] array = new int[nums.length];
            array[0] = 1;

            int max = array[0];
            for(int i = 1; i < nums.length; i++) {
                array[i] = 1;

                for(int j = 0; j < i; j++) {
                    if(nums[i] > nums[j]) {
                        array[i] = Math.max(array[j] + 1, array[i]);
                    }
                }

                max = Math.max(max, array[i]);
            }

            Util.printArray(array);
            return max;
        }
    }

    private static class Solution2 implements BaseSolution {

        @Override
        public int lengthOfLIS(int[] nums) {
            int len = 1;
            int[] array = new int[nums.length + 1];
            array[len] = nums[0];

            for(int i = 1; i < nums.length; i++) {
                if(nums[i] > array[len]) {
                    array[++len] = nums[i];
                }
                else {
                    int l = 1, r = len, pos = 0;
                    while (l <= r) {
                        int middle = (l + r) / 2;
                        if(array[middle] < nums[i]) {
                            pos = middle;
                            l = middle + 1;
                        }
                        else {
                            r = middle - 1;
                        }
                    }

                    array[pos + 1] = nums[i];
                }
            }

            return len;
        }
    }
}
